package com.apkcore.bl;

import java.util.HashMap;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * https://leetcode-cn.com/problems/max-points-on-a-line/
 * 这个题目开始一直没有看懂，懵逼。
 * 后面看了宫水三叶题解也没搞明白为什么是1和0
 * 后来走代码调试的时候，突然开窍了，这是一个x,y来表示一个坐，0就是横坐标，1是纵坐标。。。。。
 * 很多时候题目并不是太难，只是我们一直没有理解。。。
 * 加油
 */
public class _149直线上最多的点数 {

    public static void main(String[] args) {
        int[][] arr = {{1, 1}, {2, 2}, {3, 3}};
        System.out.println(new _149直线上最多的点数().maxPoints1(arr));
        String regEx = "[^0-9]";
        Pattern p = Pattern.compile(regEx);
        Matcher m1 = p.matcher("512.adfad2".substring(0, "512.adfad2".indexOf(".")));
        System.out.println(m1.replaceAll("").trim());
    }

    public int maxPoints(int[][] points) {
        int n = points.length;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int[] x = points[i];
            for (int j = i + 1; j < n; j++) {
                int[] y = points[j];
                int cut = 2;
                for (int k = j + 1; k < n; k++) {
                    int[] p = points[k];
                    int s1 = (y[1] - x[1]) * (p[0] - y[0]);
                    int s2 = (p[1] - y[1]) * (y[0] - x[0]);
                    if (s1 == s2) {
                        cut++;
                    }

                }
                ans = Math.max(ans, cut);
            }

        }

        return ans;
    }


    //////////////////////
    // 使用一个map数组，保存相同斜率下的点数
    // 使用公约数，来获取准备精度
    public int maxPoints1(int[][] ps) {
        int n = ps.length;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> map = new HashMap<>();
            int max = 0;
            for (int j = i + 1; j < n; j++) {
                int x1 = ps[i][0];
                int y1 = ps[i][1];
                int x2 = ps[j][0];
                int y2 = ps[j][1];
                int a = x1 - x2;
                int b = y1 - y2;
                int k = gcd(a, b);
                String key = (a / k) + "_" + (b / k);
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            // max+1是因为max求出的是从i出发的直线上的最多点的个数，没有包含i这个点。
            ans = Math.max(ans, max + 1);
        }
        return ans;

    }

    // 求公约数
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}
